package com.simon.study.algorithm.leetcode;

/**
 * <p>
 *
 * @author simon
 */
public class LongestPalindrom00005 {

    public static void main(String[] args) {
        String x = "xaabacxcabaaxcabaax";

        System.out.println(solution(x));
    }

    public static String solution(String s){
        int len = s.length();

        if(len < 2){ return s; }

        boolean[][] dp = new boolean[len][len];

        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = true;
        }

        int max = 1, begin = 0;
        for(int ss = 2; ss <= s.length(); ss++){
            for(int i = 0; i < s.length(); i++){

                int j = ss + i - 1;

                if(j >= s.length()){ break; }

                if(s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else{
                    if( j - i < 3 ){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if(dp[i][j] && j - i + 1 > max){
                    max = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin+max);
    }
}
